In many computer graphics applications, such as three-dimensional modeling and animation, a known problem is the building of smooth surfaces from meshes of arbitrary topology. Typically such surfaces are defined by starting with an arbitrary mesh that defines faces, vertices and edges, and their connectivity. The mesh is repeatedly subdivided to create intermediate meshes in a procedure that converges to a smooth limit surface. In practice, the intermediate meshes created are used as an approximation of the limit surface.
For meshes in which the faces are quadrilaterals, known subdivision schemes are either primal, which involves splitting faces, or dual, which involves splitting vertices, by replacing vertices with faces and faces with vertices. In general, schemes for generating an odd-degree limit surface are primal schemes using linear subdivision and a smoothing pass to compute the result. An example primal scheme, which generates a surface of degree three, is described in “Recursively Generated B-Spline Surfaces on Arbitrary Topological Meshes,” by E. Catmull and J. Clark, in Computer-Aided Design, Volume 10, Number 6 (November 1978), pages 350-355. In general, schemes for generating an even-degree limit surface are dual schemes using linear subdivision and an operation that replaces a mesh with its dual topology. An example dual scheme, which generates a surface of degree two is described in “Behaviour of recursive division surfaces near extraordinary points,” by D. Doo and M. Sabin, in Computer-Aided Design, Volume 10, Number 6 (November 1978), pages 356-360.
Several attempts have been made to unify the procedures used for creating even degree and odd degree limit surfaces. For example, Jos Stam, “On Subdivision Schemes Generalizing Uniform B-spline Surfaces of Arbitrary Degree,” Computer Aided Geometric Design—Special Edition on Subdivision Surfaces, Volume 18, pages 383-396, 2001, (“the Unified Reference”) describes a generalized method for arbitrary degree limit surfaces that uses the dual operation. However, the Unified Reference explains how to modify the generalized procedure so that for odd-degree limit surfaces, the dual operation is not required, but notes that the dual operation is still required for generating even-degree limit surfaces.
A particular problem with subdivision of a mesh in three-dimensional modeling and animation is that the mesh may have one or more properties associated with a face, edge or vertex. Example properties include but are not limited to polygon colors and texture coordinates. These properties are propagated to the subdivided topology. This propagation of properties is particularly difficult if a subdivision scheme uses the dual operation, because there is no direct correspondence between components of the original mesh and the same type of component in the dual. For example, a single face in the dual represents portions of several faces of the original mesh. If the property associated with the original faces varies from face to face, there is no single choice of value for the property for the face in the dual that correctly represents that property in the dual. A particular problem arises with texture coordinates that are used to position a texture on the surface. These coordinates are typically associated with vertices, but may vary depending on the adjacent polygon. Vertices do not have corresponding vertices in the dual, however. Therefore, if the texture coordinates vary at a vertex, then the discontinuity in the texture at the vertex cannot be properly represented in the dual.
Another problem with subdivision of a mesh is how to handle geometric boundaries and creases. A geometric boundary is an edge that has only a single adjacent face. Creases are defined on edges of the original topology and are used to add ridges to the final limit surface, as described in “Subdivision Surfaces in Character Animation,” by T. D. DeRose, M. Kass and T. Truong, in Proceedings of SIGGRAPH 98, (July 1998), pages 85-94 (the “Crease Reference”). For odd degree subdivision schemes, rules are specified for vertices lying on a boundary or crease such that the edges that form the boundary or crease converge to a curve with the same odd-degree as the limit surface. However, as noted in the Unified Reference, it is not at all clear how to add boundary and crease rules to a subdivision scheme that uses a dual operation, because the edge defining the crease or boundary does not exist in the dual topology. Also, for all meshes with geometric boundaries, the dual of the mesh has strictly fewer faces than the original mesh. As a result, if repeated dual operations are performed on a mesh, the mesh has fewer faces. If the dual operation is repeated enough times, the mesh will eventually have no boundaries or no polygons. Yet, the arbitrary degree scheme in the Unified Reference uses a dual operation repeatedly. Also, prior even-degree subdivision schemes use the dual at least once, and hence have this problem to some extent. If such boundaries and creases are needed, the Unified Reference recommends primal subdivision schemes, because they do not use the dual operation, which implies that only odd-degree surfaces can be generated when boundaries and creases are required. Current subdivision schemes also generate a limit surface with a constant degree. There is no mechanism for creating surfaces that interpolate between two limit surfaces of different degrees, or allow the target surface degree to vary over the limit surface.
The Unified Reference also notes that procedures using the dual operation are inefficient because the topology changes drastically. To remedy this inefficiency, a specialized data structure is described in “A Unified Framework for Primal/Dual Quadrilateral Subdivision Schemes”, by D. Zorin and P. Shröder, in Computer Aided Geometric Design, Volume 18, Number 5, (June 2001), pages 429-454. This data structure encodes both the mesh and its dual. Although slower because of the dual operation, the approach of the Unified Reference has the advantage that such specialized data structures are not required.
The above problems listed for surfaces also exist for the generation of curves based on polylines. A polyline is a set of vertices chained together by line segments. There are known polyline subdivision procedures that, if applied repeatedly, converge to curves of arbitrary degree. These procedures, however, suffer from the analogous problems existing with subdivision of surfaces. In particular, properties cannot be properly propagated, and there is no mechanism for interpolating between limit curves of different degrees or varying the target degree along the curve.